package ExerciseClass;
class Exercise3 {
    //主方法
    public static void main(String[] args) {
        PolynList ts = new PolynList();
        Node link1=new Node();
        Node link2=new Node();
        //第一个多项式
        ts.add(link1,3,0);
        ts.add(link1,4,2);
        ts.add(link1,-6,4);
        ts.add(link1,2,8);
        ts.add(link1,-9,11);
        ts.add(link1,3,13);
        ts.add(link1,4,15);
        //第二个多项式
        ts.add(link2,2,3);
        ts.add(link2,5,4);
        ts.add(link2,-8,7);
        ts.add(link2,9,11);

        ts.addNumber(link1, link2);

    }
}
//定义节点类
class Node{
    public int coef;//系数
    public int exp;//指数  
    public Node next=null;//下个节点  
    public Node(){
        coef=0;
        exp=0;
    }
    public Node(int coef,int exp){
        this.coef=coef;
        this.exp=exp;
    }
}

//多项式类
class PolynList {
    //添加数据方法
    public Node add(Node link,int coef,int exp) {//添加节点
        Node node=new Node(coef,exp);
        if(link==null){
            link.next=node;
        }else{
            Node temp=link;
            while(temp.next!=null){
                temp=temp.next;
            }
            temp.next=node;
        }
        return link;
    }
    //多项式相加
    public void addNumber(Node link1, Node link2) {
        Node pre=link1;
        Node qre=link2;
        Node tmep1=pre.next;//临时变量
        Node temp2=qre.next;//临时变量
        Node consquete=tmep1;
        while(tmep1!=null && temp2!=null){
            if(tmep1.exp<temp2.exp){
                pre=tmep1;
                tmep1=tmep1.next;
                //将temp1中exp小的值
            }else if(tmep1.exp>temp2.exp){
                Node temp=temp2.next;
                pre.next=temp2;
                temp2.next=tmep1;
                temp2=temp;
                //交换顺序 将x的幂次方大的往后移
            }else{
                tmep1.coef=tmep1.coef+temp2.coef;
                if(tmep1.coef==0){
                    pre.next=tmep1.next;
                    tmep1=pre.next;
                    //升序处理
                }else{
                    pre=tmep1;
                    tmep1=tmep1.next;
                    //正常移到下一个
                }
                //正常移到下一个
                qre.next=temp2.next;
                temp2=qre.next;
            }
        }
        if(temp2!=null){
            pre.next=temp2;
        }
        while(consquete!=null){
            if(consquete.exp== 0){
                System.out.print(consquete.coef);
            }else
                System.out.print(consquete.coef+"x^"+consquete.exp);
            consquete=consquete.next;
            if(consquete!=null)
                System.out.print("+");
        }
    }
}

